#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <stdexcept>
#include <assert.h>

#include "expression.h"

using namespace std;

enum Associativity {ASSOC_LEFT, ASSOC_RIGHT, ASSOC_NONE};
enum TokenType {TOKEN_NUMBER, TOKEN_VARIABLE, TOKEN_OPERATOR, TOKEN_FUNCTION, TOKEN_LEFT_BRACKET, TOKEN_RIGHT_BRACKET, TOKEN_COMMA};
#define NO_PRECEDENCE 16
#define NO_CODE_NAME ""
#define NO_ARGUMENTS 0

class ParseError : public runtime_error {
	public:
		ParseError(string const& msg) : std::runtime_error(msg) {}
};

class Token {
	public:
		Token(string nname, TokenType ntype, int nprecedence, Associativity nassoc, int nnArguments, string ncodeName) : name(nname), type(ntype), precedence(nprecedence), assoc(nassoc), nArguments(nnArguments), codeName(ncodeName), left(NULL), right(NULL) {}
		Token() {left = NULL; right = NULL;}
		~Token() {}
		size_t getNameLength() {return name.size();}
		string &getName() {return name;}
		void shunt(queue<Token *> &output, stack<Token *> &stack);
		
		//private:
		string name;
		TokenType type;
		int precedence;
		Associativity assoc;
		int nArguments;
		string codeName;
		//vector <Token *> branches;
		Token *left;
		Token *right;
};

const int nTokens = 24;
Token tokenRef[nTokens] = {	Token("+", TOKEN_OPERATOR, 1, ASSOC_LEFT, 2, "complex_add"),
							Token("-", TOKEN_OPERATOR, 1, ASSOC_LEFT, 2, "complex_sub"),
							Token("*", TOKEN_OPERATOR, 2, ASSOC_LEFT, 2, "complex_mul"),
							Token("/", TOKEN_OPERATOR, 2, ASSOC_LEFT, 2, "complex_div"),
							Token("^", TOKEN_OPERATOR, 3, ASSOC_RIGHT, 2, "complex_pow"),
							Token("(", TOKEN_LEFT_BRACKET, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, NO_CODE_NAME),
							Token(")", TOKEN_RIGHT_BRACKET, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, NO_CODE_NAME),
							Token(",", TOKEN_COMMA, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, NO_CODE_NAME),
							Token("complex", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 2, "complex_number"),
							Token("real", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "real"),
							Token("imag", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "imag"),
							Token("log", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_log"),
							Token("exp", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_exp"),
							Token("mod", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_mod"),
							Token("arg", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_arg"),
							Token("sqrt", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_sqrt"),
							Token("conj", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_conj"),
							Token("abs", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "fabs"),
							Token("sin", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_sin"),
							Token("cos", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_cos"),
							Token("tan", TOKEN_FUNCTION, NO_PRECEDENCE, ASSOC_NONE, 1, "complex_tan"),
							Token("z", TOKEN_VARIABLE, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, "z"),
							Token("c", TOKEN_VARIABLE, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, "c"),
							Token("i", TOKEN_VARIABLE, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, "complex_number(0,1)")
								
};


// check if the string contains a number..
// it must be able to accept appropriate decimal points and + and - prefixes.
static Token *readNumber(string expr, queue <Token *> *tokens) {
	//int minus = 0;
	//int plus = 0;
	int decimal = 0;
	int digit = 0;
	int i;
	
	int canBeUnary = 0;
	
	// find out if we are expecting a unary operator.
	if (tokens->empty()) {
		canBeUnary = 1;
	} else {
		if ((tokens->back()->type == TOKEN_OPERATOR) || (tokens->back()->type == TOKEN_LEFT_BRACKET) || (tokens->back()->type == TOKEN_COMMA)) {
			canBeUnary = 1;
		}
	}
	
	for (i = 0; i < expr.length(); i++) {
		if (expr[i] == '-') {
			if ((i == 0) && (canBeUnary)) {
				//minus = 1;
			} else {
				break;
			}
		} else 
		if (expr[i] == '+') {
			if ((i == 0) && (canBeUnary)) {
				//plus = 1;
			} else {
				break;
			}
		} else
		if (expr[i] == '.') {
			if (decimal == 0) {
				decimal = 1;
			} else {
				break;
			}
		} else if (isdigit(expr[i])) {
			digit = 1;
		} else {
			break;
		}
	}	
	if (digit) {
		string num = expr.substr(0, i);
		string codeName = "complex_number(";
		codeName += num;
		codeName += ",0)";
		//std::cout << "number: " << num << endl;
		return new Token(num, TOKEN_NUMBER, NO_PRECEDENCE, ASSOC_NONE, NO_ARGUMENTS, codeName);
	}
	return NULL;
}

// rules
// +/- are unary when there is another operator or opening bracket before them

// if (number||variable||FUNCTION) and the last token 

bool isAValue(TokenType type) {
	return ((type == TOKEN_NUMBER) || (type == TOKEN_VARIABLE) || (type == TOKEN_FUNCTION));
}

static Token *read(string expr, queue <Token *> *tokens, size_t *length) {
	Token *token = NULL;
	// first check if the token is a number;
	token = readNumber(expr, tokens);
	if (token != NULL) {
		*length = token->getNameLength();
		return token;
	}
	
	for (int i = 0; i < nTokens; i++) {
		if (expr.find(tokenRef[i].getName()) == 0) {
			if (isAValue(tokenRef[i].type)) {
				if ((!tokens->empty()) && isAValue(tokens->back()->type)) {
					*length = 0;
					// FIXME: hard coded value for multiply
					return new Token(tokenRef[2]);
				}
			}
			/*
			if (tokenRef[i].type == TOKEN_OPERATOR) {
				if ((tokens->empty()) || (tokens->back()->type == TOKEN_OPERATOR)) {
					throw ParseError("unexpected operator");
				}
			}
			*/
			*length = tokenRef[i].getNameLength();
			return new Token(tokenRef[i]);
		}
	}
	return NULL;
}

static queue <Token *> *createTokensList(string expression) {
	queue <Token *> *tokens = new queue <Token *>;
	while(expression.length() > 0) {
		// erase spaces
		if (expression[0] == ' ') {
			expression.erase(0, 1);
			continue;
		}
		size_t length = 0;
		Token *token = read(expression, tokens, &length);
		if (token == NULL) {
			while(tokens->size()) {
				Token *t = tokens->front();
				delete t;
				tokens->pop();
			}
			cerr << "bad token: " << expression[0] << endl;
			throw ParseError("bad token");
			return NULL;
		}
		//cout << token->name << " ";
		tokens->push(token);
		//cout << "len " << length << " ";
		expression.erase(0, length);
	}
	
	/*
	if ((tokens->back()->type == TOKEN_OPERATOR) || (tokens->back()->type == TOKEN_FUNCTION)) {
		throw ParseError("unexpected operator or function at end of expression");
	}
	*/
	
	return tokens;
}

void linkOperands(Token *token, stack<Token *> &output) {
	if (token->type == TOKEN_OPERATOR) {
		//token->branches.push_back(output.top());
		if (output.size() < 2) {
			std::string msg("operator has insufficient operands: ");
			msg += token->name;
			throw ParseError(msg);
		}
		token->right = output.top();
		output.pop();
		token->left = output.top();
		output.pop();
	} else 
	if (token->type == TOKEN_FUNCTION) {
		if (output.size() < token->nArguments) {
			std::string msg("function has insufficient arguments: ");
			msg += token->name;
			throw ParseError(msg);
		}
		
		if (token->nArguments == 1) {
			token->left = output.top();
			output.pop();
		} else
		if (token->nArguments == 2) {
			token->right = output.top();
			output.pop();
			token->left = output.top();
			output.pop();
		}

	} else {
		assert(0 && "bad token type");
	}
}

void shunt(Token *token, stack<Token *> &output, stack<Token *> &stack) {
	switch(token->type) {
		case TOKEN_NUMBER:
			output.push(token);
			break;
		case TOKEN_VARIABLE:
			output.push(token);
			break;
		case TOKEN_OPERATOR:
			while(!stack.empty() && stack.top()->type == TOKEN_OPERATOR) {
				Token *topToken = stack.top();
				if ((token->precedence < topToken->precedence) || 
					((token->precedence == topToken->precedence) && 
						(token->assoc == ASSOC_LEFT))) {
					stack.pop();
					linkOperands(topToken, output);
					output.push(topToken);
				} else {
					break;
				}
			}
			stack.push(token);
			break;
		case TOKEN_FUNCTION:
			stack.push(token);
			break;
		case TOKEN_LEFT_BRACKET:
			stack.push(token);
			break;
		case TOKEN_RIGHT_BRACKET:
			while (1) {
				if (stack.empty()) {
					throw ParseError("bracket mismatch: missing (");
				}
				Token *topToken = stack.top();
				if (topToken->type == TOKEN_LEFT_BRACKET) {
					stack.pop();
					if (!stack.empty()) {
						topToken = stack.top();
						if (topToken->type == TOKEN_FUNCTION) {
							stack.pop();
							linkOperands(topToken, output);
							output.push(topToken);
						}
					}
 					break;
				}
				stack.pop();
				linkOperands(topToken, output);
				output.push(topToken);
			}
			break;
		case TOKEN_COMMA:
			while (1) {
			if (stack.empty()) {
				throw ParseError("comma with missing (");
			}
			Token *topToken = stack.top();
			if (topToken->type == TOKEN_LEFT_BRACKET) {
				//stack.pop();
				break;
			}
			stack.pop();
			linkOperands(topToken, output);
			output.push(topToken);
		}
		break;
	}
}

static void shuntingYard(string expression, stack <Token *> &output) {
	// first, we generate an array of tokens from the string
	queue <Token *> *tokens = createTokensList(expression);
	stack <Token *> operatorStack;
	
	while(tokens->size() > 0) {
		Token *token = tokens->front();
		shunt(token, output, operatorStack);
		tokens->pop();
	}
	
	while(!operatorStack.empty()) {
		Token *token = operatorStack.top();
		if (token->type == TOKEN_LEFT_BRACKET) {
			throw ParseError("mismatched brackets: missing )");
		}
		operatorStack.pop();
		linkOperands(token, output);
		output.push(token);
	}
	
	/*
	stack <Token *> temp = output;
	while(!temp.empty()) {
		Token *token = temp.top();
		temp.pop();
		cout << token->name << " ";
	}
	cout << endl;
	*/
	
	delete tokens;
}

void generate(Token *token, string &code) {
	switch(token->type) {
		case TOKEN_NUMBER:
			code += token->codeName;
			break;
		case TOKEN_VARIABLE:
			code += token->codeName;
			break;
		case TOKEN_OPERATOR:
			code += token->codeName;
			code += "(";
			generate(token->left, code);
			code += ",";
			generate(token->right, code);
			code += ")";
			break;
		case TOKEN_FUNCTION:
			code += token->codeName;
			code += "(";
			if (token->nArguments == 1) {
				generate(token->left, code);
			} else {
				generate(token->left, code);
				code += ",";
				generate(token->right, code);
			}
			code += ")";
			break;
		default:
		break;
	}
	delete token;
}


void printTree(Token* t, int indent = 0) {
	if(t != NULL) {
		for (int i = 0; i < indent; i++) {
			cout << '\t';
		}
		cout << t->name << "\n";
		if(t->left) printTree(t->left, indent + 1);
		if(t->right) printTree(t->right, indent + 1);
	}
}


std::string compile(char *expression) {
	//char *code = new char[8096];
	std::string code;
	stack <Token *> output;
	shuntingYard(expression, output);
	//printTree(output.top());
	code += "z = ";
	generate(output.top(), code);
	code += ";";
	return code;
}


